<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
      const height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

      // 按行求
      // 时间复杂度：如果最大的数是 m，个数是 n，那么就是 O(m*n)O(m∗n)。空间复杂度：O(1)O(1)。
      var trap = function (height) {
        const maxHeight = Math.max(...height);
        let ans = 0;
        for (let i = 1; i <= maxHeight; i++) {
          let start = false;
          let tem = 0;

          for (let j = 0; j < height.length; j++) {
            if (height[j] >= i) {
              start = true;
              ans = ans + tem;
              tem = 0;

              continue;
            }
            if (start && height[j] < i) {
              tem++;
            }
          }
        }
        return ans;
      };

      // 按列求
      // 0 1 2 3 4 5
      var trapByColumn = function (height) {
        let res = 0;
        for (let i = 1; i < height.length - 1; i++) {
          let left_max = 0;
          let right_max = 0;
          // 找到左边比它高的值
          for (let j = i - 1; j >= 0; j--) {
            if (height[j] > left_max) {
              left_max = height[j];
            }
          }

          for (let j = i + 1; j <= height.length; j++) {
            if (height[j] > right_max) {
              right_max = height[j];
            }
          }
          const min = Math.min(left_max, right_max);
          if (min > height[i]) {
            res = res + (min - height[i]);
          }
        }
        return res;
      };

      var trap3 = function (height) {
        let sum = 0;
        const max_left = new Array(height.length).fill(0);
        const max_right = new Array(height.length).fill(0);
        for (let i = 1; i < height.length - 1; i++) {
          max_left[i] = Math.max(height[i - 1], max_left[i - 1]);
        }
        for (let i = height.length - 2; i >= 0; i--) {
          max_right[i] = Math.max(height[i + 1], max_right[i + 1]);
        }
        for (let i = 1; i < height.length - 1; i++) {
          const min = Math.min(max_left[i], max_right[i]);
          if (min > height[i]) {
            sum = sum + (min - height[i]);
          }
        }
        return sum;
      };

      //双指针
      var trap4 = function (height) {
        let ans = 0;
        let left = 0,
          right = height.length - 1;
        let leftMax = 0,
          rightMax = 0;
        while (left < right) {
          leftMax = Math.max(leftMax, height[left]);
          rightMax = Math.max(rightMax, height[right]);
          if (height[left] < height[right]) {
            ans += leftMax - height[left];
            ++left;
          } else {
            ans += rightMax - height[right];
            --right;
          }
        }
        return ans;
      };

      //   height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
      /*  单调栈 */
      var trap5 = function (height) {
        let ans = 0;
        const stack = [];

        for (let i = 0; i < height.length; i++) {
          while (stack.length && height[i] > height[stack[stack.length - 1]]) {
            const top = stack.pop();
            if (!stack.length) break;
            const left = stack[stack.length - 1];
            const width = i - left - 1;
            const curHeight = Math.min(height[left], height[i]) - height[top];
            ans += width * curHeight;
          }
          stack.push(i);
        }
        return ans
        // let ans = 0;
        // const stack = [];
        // const n = height.length;
        // for (let i = 0; i < n; ++i) {
        //   while (stack.length && height[i] > height[stack[stack.length - 1]]) {

        //     const top = stack.pop();
        //     if (!stack.length) {
        //       break;
        //     }
        //     const left = stack[stack.length - 1];
        //      if(i===3){
        //        debugger
        //      }

        //     const currWidth = i - left - 1;

        //     const currHeight = Math.min(height[left], height[i]) - height[top];
        //     ans += currWidth * currHeight;

        //   }
        //   stack.push(i);
        // }
        // return ans;
      };

      console.log(trap(height));
      console.log(trapByColumn(height));
      console.log(trap3(height));
      console.log(trap5([0,1,0,2,1,0,1,3,2,1,2,1]));
    </script>
  </body>
</html>
